# 增加：添加节点，在n1和n2之间加一个新节点n，
# n1.next = n  n.next = n2   下一个节点指向
# n2.prev = n  n.prev = n1   上一个节点指向
import cmath,math

class Node:
    def __init__(self, data=None):
        self._data = data
        self.next = None
        self.prev = None

    @property
    def data(self):
        return self._data

    @data.setter
    def data(self, data):
        self._data = data


class LinkedListDouble:
    def __init__(self):
        self.head = Node()
        self.tail = Node()
        self.length = 0

        self.head.next = self.tail
        self.tail.prev = self.head

    def findposition(self, pos):
        assert 0 <= pos <= self.length
        if pos <= math.ceil(self.length // 2):
            tempPtr = self.head
            while pos > 0:
                tempPtr = tempPtr.next
                pos -= 1
            return tempPtr
        else:
            tempPtr = self.tail
            while pos <= self.length:
                tempPtr = tempPtr.prev
                pos += 1
            return tempPtr

    def insertEle(self, data, pos):
        tempPtr = self.findposition(pos)
        prevNode = tempPtr
        nextNode = tempPtr.next

        newNode = Node()
        newNode.data = data

        prevNode.next = newNode
        newNode.prev = prevNode

        # if nextNode is not None:
        newNode.next = nextNode
        nextNode.prev = newNode
        self.length += 1

    def appendEle(self,data):
        self.insertEle(data, self.length)

    def popEle(self,pos):
        tempPtr = self.findposition(pos)
        nextNode = tempPtr.next.next
        tempPtr.next = nextNode
        nextNode.prev = tempPtr
        self.length -= 1

    def forEle(self):
        assert self.length > 0
        tempPtr = self.head.next
        while tempPtr is not None:
            yield tempPtr.data
            tempPtr = tempPtr.next

    def __iter__(self):
        return self.forEle()

    def __len__(self):
        return self.length

    def __getitem__(self, pos):
        tempPtr = self.findposition(pos)
        return tempPtr.next.data

    def __setitem__(self, key, value):
        tempPtr = self.findposition(key)
        tempPtr.next.data = value

    def __delitem__(self, key):
        self.popEle(key)


def print_iter(x):
    for v in l:
        print(v)


if __name__ == "__main__":
    l = LinkedListDouble()
    l.insertEle(5, 0)
    l.insertEle(6, 1)
    l.insertEle(7, 1)
    l.appendEle(99)
    l[3] = 88
    del l[0]
    # for v in l:
    #     print(v)
    print_iter(l)



